笔记分享|浙大暑期密码学课程：Idealized Model l
上篇笔记是针对Hong-Sheng Zhou老师在浙江大学的暑期Crypto School的《浙大Universal Composability Ⅰ（ 上）》，详情请见笔记分享|浙大暑期密码学课程：通用可组合性（1）。
本篇笔记对张聪老师在浙江大学的暑期Crypto School的《Idealized Model l》课程进行了整理，可前往以下b站链接或点击下列视频观看完整课程。
浙大暑期Crypto课程- ldealized Models l（上)-Cong Zhang
https://www.bilibili.com/video/BV1gg4y1w7xQ/?spm_id_from=333.788&vd_source=15b7926a3a203446fa868f18be9bc87e
浙大暑期Crypto课程- ldealized Models l（下)-Cong Zhang
https://www.bilibili.com/video/BV1BP411C7Wj/?spm_id_from=333.788&vd_source=15b7926a3a203446fa868f18be9bc87e
前言
关于Idealized Model的课程主要围绕以下Theorem展开:
Theorem: If X holds, then Y(X) is secure in Model M.
To make things simple:
(1). Ignore M: think of M as a part of the definition of Y.
(2). Standard computational model: TMs/circuits.
可以看到给出了两个限制，我们将一步步把这些限制放回去。
类似于哲学问题“我是谁”“我来自哪里”“我到哪里去”，对于Random Oracle也可以提出类似的问题“什么是Random Oracle”，“它是如何sample得到的”，“它如何使用（seperation, proof, construction等）。
什么是Random Oracle (RO)
对于这个问题，可能很多人都会回答“它是一个关于哈希的‘神话’”，但是为什么用了这个“神话”我们就能轻易进行证明了呢？
标准模型（Stand Model）包含所有图灵机的算法，是一个算法集，其反映了我们现实世界中的模型。然而在该模型下无法达到某些要求，因此我们考虑对攻击者算法进行一些限制，使得安全证明能够顺利进行，这就是我们使用“神话”RO的原因。
RO本身不能计算哈希函数，而是通过问询（Query）得到回答（Response），因此在进行query之前无法得到response，给了我们在reduction中的控制权。
例如A输出x要得到输入h(x)，在把x给reduction R后，R调用一个RO进行计算，使得整体reduction仍在Stand Model下，而A受限于RO。
RO是如何得到的
一般来说，RO是一个真随机的哈希函数，定义为RO ，一般有两种方法得到。
一种是inefficient的。在初始化时就sample出映射表，每查询时进行查表即可。
另一种是Lazy-Sampling，初始化时保存空表，每次查询时判断查询值是否在表中，如果在，则返还对应的值，否则随机生成值并记录在表中。
可以看到，第二种方法可以在ppt时间以及poly-space内完成，是涵盖在Stand Model下的，而这两种方法是不可区分的。
首先对于简单的映射,我们可以列出所有从n到n的映射的函数，然后以1/s的概率从s个函数中随机选取一个，这显然是真随机。
然而对于映射，依照上面的方法，将会列出无穷个映射函数，从中随机选得任意一个函数的概率都趋近于0，需要考虑其他方法。对于原像的长度*，虽然是任意的，但仍然是有限长度的，因此可以考虑以下构造以下集合
从每个集合中各sample一个结果，记为，则RO≔kgk，其中k为无穷。
RO的使用方法
考虑Theorem： such that A breaks “key-recovery”，意思是可以构建一个攻击者A，对于任意关于RO的构造，都能攻破其“key-recovery”的特征。(1). 攻击者: 对于A我们有以下需求：
(1). Unbounded computation power
(2). PPT memory
(3). Bounded query to RO
(4). Breaks Key-Recovery
下面是对以上需求的阐释：
对于①，若改成PPT computation power，会导致复杂度出现分层，难以处理。并且，若攻击者是PPT的，将无法确保只用RO进行构造。
②属于技术要求。关于
③，若是unbounded，可以进行无限问询，则将能轻易破解“key-recovery”。
(2). 攻击过程 有了攻击者，下面我们考虑如何进行攻击。
对于Alice和Bob，他们各自有sk，攻击者需要在只知道Trans以及拥有对RO有限的问询权限的情况下猜出shared key。
以下为攻击步骤（假设攻击Alice，Bob最多对RO进行次query）：
Step1：用伪造的无限oracle RO’猜出所有满足所有Trans的，设满足条件的密钥为，RO为，得到Shared key 。
Step2：再次用伪造的RO’猜出所有满足所有Trans的，若某次问询的是step1中对RO query过的值，则用对应的真值作为回答，得到新的，并对RO query相同的值，放入真值表。
：重复上述迭代步骤。最后得到个k，以出现次数最多的值作为输出。
正确性：我们声明[1]，对于得到的个k，从第个k开始就能得到正确的值，因此出现次数最多的值就是真正的Shared key。
下证该声明的正确性。构造一个，对于Bob的query，调用RO回答真值，对于Alice的query，调用RO’回答，即只需满足与Trans对应。以此构建，获得。不需要与真实的一致。由于在真实的RO中，两方得到的Shared key一致，都是真实的。
因此在此构造中得到的也与真实的Shared key一致。令为Alice对进行的query，为Bob对RO进行的query，E为真值表。则每轮存在两种情况：
Case1：，则将该元素加入E
Case2：由于Bob最多query 次，因此轮后全为Case2，既满足Trans也满足Bob的query，因此轮后得到的也与真实的Shared key一致。
(PS：笔记里是作者自己整理，可能会有一些不太准确的表达，也会有一些不当的理解，欢迎大家在留言区指出，一起学习交流)
往期推荐
1.学习同态加密：第二代全同态加密经典论文合集
2.学习同态加密：第一代全同态加密经典论文合集文章速览 | 联邦学习 x AAAI'2023 （下）4.深入浅出零知识证明（二）：电路模型概述